﻿#include<iostream>
#include<bitset>
using namespace std;
const int MAX = 4e5;
/*
	学习视频--理论    （1）https://haokan.baidu.com/v?vid=12119840319122444001&pd=bjh&fr=bjhauthor&type=video
	八数码问题有解性的规则：初始状态和目标状态的逆序奇偶性是否相同，是则有解
	学习视频--简单广搜（2）https://haokan.baidu.com/v?vid=14713378919712858526&pd=bjh&fr=bjhauthor&type=video
	学习视频--优化    （3）https://haokan.baidu.com/v?vid=13156182900857134098&pd=bjh&fr=bjhauthor&type=video
	测试网站：http://poj.org/problem?id=1077，
	测试案例：输入： 2  3  4  1  5  x  7  6  8 ,输出：ullddrurdllurdruldr
	POJ测试： 2824K,672MS
	康托展开公式：X = A_n *(n-1)!+A_(n-1) *(n-2)! +...+a1*0!,其中,A_i表示后面元素比第i位数字小的个数，即第i位在未出现的元素中是排在第几个
*/
struct Node {
	int status;			//状态，排列的编号
	int father;			//父节点指针
	char move;			// 父节点到本节点的移动方式 u/d/l/r
	Node() {}
	Node(int s, int f, char c) :status(s), father(f), move(c) {}
};

int goalState;			//目的状态序号，"123456780"对应的排列号
bitset<362880>Flags;	//节点是否被访问过的标志，9! = 362880
char result[MAX];		//结果	
Node myqueue[MAX];		//状态列表
int qHead, qTail;		//头指针和尾指针
char sz4Moves[] = "udrl";// 4种移动方向
const char* zeroStrStatus = "012345678";// 0号排列
const char* endStrStatus = "123456780";// 0号排列
unsigned int factorial[21];//存放0-20的阶乘，unsigned类型存储不了21的阶乘，本实验用到9！而已

// 排列-> 序号
template<class T>
unsigned int GetPermutationNum(T* first, T* second, int len) {
	// 1、second->分割成整数数组的元素
	// first是0号排列，second是目标排列
	int perInt[21];			// 阶乘最大存储到20，题目不可能需要那么多空间
	int i, j;
	for (i = 0; i < len; i++) {
		for (j = 0; j < len; j++) {
			if (*(first + j) == *(second + i)) {
				perInt[i] = j;
				break;
			}
		}
	}
	// 2、通过数组求排列对应的序号,数组每一位以对应阶乘存储，可以省略很多有重复数字组成的数字的空间
	unsigned int num = 0;
	bool used[21] = { 0 };
	for (i = 0; i < len; i++) {
		unsigned int n = 0;
		for (j = 0; j < perInt[i]; j++) {
			if (!used[j]) ++n;
		}
		num += n * factorial[len - i - 1];
		used[j] = true;
	}
	return num;
}

int StrStatusToIntStatus(const char* strStatus) {
	return GetPermutationNum(zeroStrStatus, strStatus, 9);
}

// 序号->排列
template<class T>
void GenPermutation(T* first, T* second, int len, unsigned int No) {
	int perInt[21];
	bool used[21] = { 0 };
	int i, j;
	// 1、通过和高阶阶乘比较，找出对应的值
	for (i = 0; i < len; i++) {
		int n = 0;
		for (j = 0; j < len; j++) {
			if (!used[j]) {
				if (factorial[len - i - 1] - 1 >= No) break;
				else
					No -= factorial[len - i - 1];
			}
		}
		perInt[i] = j;
		used[j] = true;
	}
	// 2、在0号排列中增加序号，得到对应的排列
	for (i = 0; i < len; i++)
		*(second + i) = *(first + perInt[i]);
}

void IntStatusToStrStatus(unsigned int IntStatus, char* StrStatus) {
	GenPermutation((char*)zeroStrStatus, StrStatus, 9, IntStatus);
}

// 创造新的状态序号
unsigned int NewStatus(int nStatus, char move) {
	//求从nStatus经过cMove移动后得到的新状态。若移动不可行则返回-1
	char szTmp[20]; int zeroIndex = 0;
	IntStatusToStrStatus(nStatus, szTmp);
	// 1、找到'0'的下标
	for (int i = 0; i < 9; i++) {
		if (szTmp[i] == '0') {
			zeroIndex = i;
			break;
		}
	}
	// 2、通过判断zeroIndex+move的范围确定移动是否可以
	switch (move) {
	case 'u':
		if (zeroIndex < 3) return -1;
		else {
			szTmp[zeroIndex] = szTmp[zeroIndex - 3];
			szTmp[zeroIndex - 3] = '0';
		}
		break;
	case 'd':
		if (zeroIndex + 3 > 8) return -1;
		else {
			szTmp[zeroIndex] = szTmp[zeroIndex + 3];
			szTmp[zeroIndex + 3] = '0';
		}
		break;
	case 'l':
		if (zeroIndex % 3 == 0) return -1;
		else {
			szTmp[zeroIndex] = szTmp[zeroIndex - 1];
			szTmp[zeroIndex - 1] = '0';
		}
		break;
	case 'r':
		if (zeroIndex % 3 == 2) return -1;
		else {
			szTmp[zeroIndex] = szTmp[zeroIndex + 1];
			szTmp[zeroIndex + 1] = '0';
		}
		break;
	}

	return StrStatusToIntStatus(szTmp);
}

bool bfs(int Status) {
	qHead = 0, qTail = 1;		//头指针和尾指针
	Flags.reset();			// 标签数组清空初始化
	myqueue[qHead] = Node{ Status,-1,0 };
	while (qHead != qTail) {
		int nStatus = myqueue[qHead].status;
		if (nStatus == goalState) return true;
		for (int i = 0; i < 4; i++) {
			int newStatus = NewStatus(nStatus, sz4Moves[i]);
			// 1、判断范围
			if (newStatus == -1) continue;
			// 2、判断是否重复
			if (Flags[newStatus]) continue;
			myqueue[qTail++] = Node{ newStatus,qHead,sz4Moves[i] };
			Flags.set(newStatus, true);
		}
		qHead++;
	}
	return false;
}

int main() {
	std::ios::sync_with_stdio(false); // 加快输入输出
	// 1、初始化阶乘数组和目标状态
	factorial[0] = factorial[1] = 1;
	for (int i = 2; i < 21; i++) {
		factorial[i] = i * factorial[i - 1];
	}
	goalState = StrStatusToIntStatus(endStrStatus);	//例如："123456780"对应的编号是 46233
	// 2、获得输入字符串，并进行可行性判断

	char szLine1[50], szLine2[20]; // szLine1获得输入流的所有字符，szLine2筛选出字符串
	while (cin.getline(szLine1, 48)) {
		// 筛选和替换
		int i, j;
		for (i = 0, j = 0; szLine1[i]; i++) {
			if (szLine1[i] == ' ')  continue;
			if (szLine1[i] == 'x' || szLine1[i] == 'X' || szLine1[i] == '0') szLine2[j++] = '0';
			else szLine2[j++] = szLine1[i];
		}
		szLine2[j] = 0;
		// 判断可行性规则：
		//  一个状态表示成一维的形式，求出除0之外所有数字的逆序数之和，也就是每个数字前面比它大的数字的个数的和，称为这个状态的逆序
		// 若两个状态的逆序奇偶性相同，则可相互到达，否则不可相互到达。	由于原始状态的逆序为0（偶数），则逆序为偶数的状态有解
		int initSum = 0, testSum = 0;

		char* szLine3 = (char*)"123456780";
		for (int i = 0; i < 9; i++) {
			if (szLine3[i] == '0') continue;
			for (int j = 0; j < i; j++) {
				initSum += szLine3[j] != '0' && szLine3[j] > szLine3[i] ? 1 : 0;
			}
		}
		for (int i = 0; i < 9; i++) {
			if (szLine2[i] == '0') continue;
			for (int j = 0; j < i; j++) {
				testSum += szLine2[j] != '0' && szLine2[j] > szLine2[i] ? 1 : 0;
			}
		}
		if (initSum % 2 != testSum % 2) {	//逆序奇偶性不相同
			cout << "unsolvable" << endl;
			continue;
		}
		if (bfs(StrStatusToIntStatus(szLine2))) {
			// 输出结果
			int nPos = qHead;
			int nMoves = 0;
			do {
				result[nMoves++] = myqueue[nPos].move;
				nPos = myqueue[nPos].father;
			} while (nPos);
			// 逆序
			for (int j = nMoves - 1; j >= 0; j--) {
				cout << result[j];
			}
		}
		else {
			cout << "unsolvable" << endl;
		}
	}
}

